//************************************************************
//    > File Name: balanced-binary-tree.cpp
//    > Author: davis
//    > Mail:  
//    > Created Time: 2017年03月27日 10:04:05
//***********************************************************
//lintcode #93
#include<bits/stdc++.h>
using namespace std;
class TreeNode {
	public:
		int val;
		TreeNode *left,*right;
		TreeNode(int val=-1){
			this->val=val;
			this->left=this->right=NULL;
		}
};
int getDepth(TreeNode *r){
	if(r==NULL) return 0;
	int left=getDepth(r->left);
	int right=getDepth(r->right);
	return left>right?left+1:right+1;

}
bool isBalanced(TreeNode *root){
	if(root==NULL) return true;
	int left=getDepth(root->left);
	int right=getDepth(root->right);
	if(abs(left-right)>1) return false;
	return isBalanced(root->left)&&isBalanced(root->right);
}
int main(){
	TreeNode *a=new TreeNode[3];
	a[1].val=1;
	a[2].val=2;
	a[3].val=3;
	a[1].left=&a[2];
	a[1].right=&a[3];
	cout<<isBalanced(a)<<endl;

	delete[] a;
}
